{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures - Doubly Linked Lists\n",
    "\n",
    "A doubly linked list is an extension of a single linked list, but now instead of each node only having a single pointer that points forward, there is an additional pointer that points to the previous node. Visually we can think of a node like the following:\n",
    "\n",
    "<img src=\"DoubleLinkedLists - Node.png\" width=\"300\">\n",
    "\n",
    "A collection of these nodes is called a list, and can be visualized as the following:\n",
    "\n",
    "<img src=\"DoubleLinkedList - List.png\" width=\"500\">\n",
    "\n",
    "The first node is a particular node that we call the head, or in other words, it is the first chain in the link of nodes.\n",
    "\n",
    "\n",
    "### Advantages Over Singly Linked Lists\n",
    "1. Can be traversed in both forward and backward direction.\n",
    "2. The delete operation in DLL is more efficient if the pointer to the node to be deleted is given.\n",
    "3. We can quickly insert a new node before a given node.\n",
    "\n",
    "\n",
    "### Disadvantages Over Singly Linked Lists\n",
    "1. Every node of DLL Requires extra space for a previous pointer. \n",
    "2. All operations require an additional pointer previous to be maintained. \n",
    "\n",
    "\n",
    "## Performance\n",
    "\n",
    "| Data Structure | Average Insert | Average Delete | Average Search | Worst Insert | Worst Delete | Worst Search |\n",
    "|----------------|----------------|----------------|----------------|--------------|--------------|--------------|\n",
    "| Doubly Linked List    | O(1)           | O(1)           | O(n)           | O(1)         | O(1)         | O(n)         |\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# defining our node object\n",
    "class Node(object):\n",
    "    \n",
    "    def __init__(self, data = None, next_node = None, prev_node = None):\n",
    "        \n",
    "        # our node has three properties, a piece of data, a pointer to the next node, and a pointer to the previous node.\n",
    "        self.data = data\n",
    "        self.next_node = next_node\n",
    "        self.prev_node = prev_node\n",
    "        \n",
    "    def get_data(self):        \n",
    "        return self.data\n",
    "    \n",
    "    def get_next(self):\n",
    "        return self.next_node\n",
    "\n",
    "    def get_prev(self):\n",
    "        return self.prev_node\n",
    "\n",
    "    def set_next(self, new_next):\n",
    "        self.next_node = new_next\n",
    "        \n",
    "    def set_prev(self, new_prev):\n",
    "        self.prev_node = new_prev\n",
    "        \n",
    "\n",
    "class DoubleLinkedList(object):\n",
    "    \n",
    "    def __init__(self, head = None, end = None):\n",
    "        self.head = head\n",
    "        \n",
    " \n",
    "\n",
    "    def traverse(self):\n",
    "        '''\n",
    "            Traverse the list and print each value.\n",
    "            Time Complexity: O(n)\n",
    "        '''\n",
    "        \n",
    "        # grab the first node.\n",
    "        curr_node = self.head\n",
    "        \n",
    "        # keep going until you reach the end of the list\n",
    "        while curr_node != None:\n",
    "            \n",
    "            # print the piece of data and set the current node equal to the next node.\n",
    "            print(curr_node.data)            \n",
    "            curr_node = curr_node.next_node\n",
    "            \n",
    "            \n",
    "    def get_list_size(self):\n",
    "        '''\n",
    "            Returns the size of the list\n",
    "            Time Complexity: O(n), also if you think about it you could calculate it once store it as a property.\n",
    "                             Then when you insert/delete the node you just update the count. This would make it an O(1)\n",
    "                             operation.\n",
    "        '''\n",
    "\n",
    "        count = 0\n",
    "        \n",
    "         # grab the first node.\n",
    "        curr_node = self.head\n",
    "        \n",
    "        # keep going until you reach the end of the list\n",
    "        while curr_node != None:\n",
    "            \n",
    "            # print the piece of data and set the current node equal to the next node.\n",
    "            count = count + 1            \n",
    "            curr_node = curr_node.next_node  \n",
    "            \n",
    "        return count\n",
    "            \n",
    "            \n",
    "    def insert_beg(self, data):\n",
    "        '''\n",
    "            Insert a node at the beginning of our list, at the head.\n",
    "            Time Complexity: O(1)\n",
    "        '''\n",
    "        \n",
    "        # define a new node\n",
    "        new_node = Node(data)\n",
    "        \n",
    "        # set the next node to old head\n",
    "        new_node.next_node = self.head\n",
    "        \n",
    "        # because it's the head it will have no previous node.\n",
    "        new_node.prev_node = None\n",
    "        \n",
    "        # handle the empty list case\n",
    "        if self.head != None:               \n",
    "            self.head.set_prev(new_node)\n",
    "        \n",
    "        # update the head property.\n",
    "        self.head = new_node\n",
    "\n",
    "        \n",
    "        \n",
    "    def insert_end(self, data):\n",
    "        '''\n",
    "            Insert a node at the end of our list.\n",
    "            Time Complexity: O(n), I have to find the end first then delete. The delete operation is O(1),\n",
    "                             but the access is O(n).\n",
    "        '''\n",
    "        \n",
    "        # define a new node.\n",
    "        new_node = Node(data)  \n",
    "        \n",
    "        # it's at the end of our list, so there is no node after it.\n",
    "        new_node.next_node = None\n",
    "        \n",
    "        # handle the empty list scenario.\n",
    "        if self.head == None: \n",
    "            new_node.prev_node = None\n",
    "            self.head = new_node\n",
    "            return\n",
    "        \n",
    "        # otherwise, grab the first node.\n",
    "        first_node = self.head\n",
    "        \n",
    "        # loop to till you find the end.\n",
    "        while first_node.next_node:\n",
    "            first_node = first_node.next_node\n",
    "\n",
    "        # when at the end, set the next node equal to new node.\n",
    "        first_node.set_next(new_node)\n",
    "        new_node.prev_node = first_node\n",
    "\n",
    " \n",
    "\n",
    "    def insert_before(self, ref_node, data):\n",
    "        '''\n",
    "            Insert a node before a given reference node.\n",
    "            Time Complexity: O(1)\n",
    "        ''' \n",
    "        \n",
    "        if self.head is None:\n",
    "            print(\"List is empty\")\n",
    "            return             \n",
    "        \n",
    "        # define a new node.\n",
    "        new_node = Node(data)\n",
    "        \n",
    "        # set the next node of the new node to the old node.\n",
    "        \n",
    "        # set the new_node's prev_node to the reference node's previous node\n",
    "        new_node.prev_node = ref_node.prev_node  \n",
    "        \n",
    "        # have the reference node pevious node point to the new node.\n",
    "        ref_node.prev_node = new_node\n",
    "        \n",
    "       # have the new node's next node point to the reference node.\n",
    "        new_node.next_node = ref_node\n",
    "        \n",
    "        # if it's not the head\n",
    "        if new_node.prev_node != None:\n",
    "            # have the ref node's old previous node now point to the new node.\n",
    "            new_node.prev_node.next_node = new_node\n",
    "        else:\n",
    "            self.head = new_node\n",
    "\n",
    " \n",
    "\n",
    "    def insert_after(self, ref_node, data):\n",
    "        '''\n",
    "            Insert a node after a given reference node.\n",
    "            Time Complexity: O(1)\n",
    "        '''  \n",
    "        \n",
    "        # define a new node\n",
    "        new_node = Node(data)\n",
    "        \n",
    "        # have the next node of the new node equal the reference node's next node.\n",
    "        new_node.next_node = ref_node.next_node \n",
    "        \n",
    "        # now point the ref node's next node point to the new node\n",
    "        ref_node.next_node = new_node\n",
    "        \n",
    "        # have the new node previous node equal the reference node.\n",
    "        new_node.prev_node = ref_node\n",
    "        \n",
    "        # if we aren't at the end of the list then make sure to have the node after the new node\n",
    "        # point to the new node\n",
    "        if new_node.next_node is not None:\n",
    "            new_node.next_node.prev_node = new_node\n",
    "            \n",
    " \n",
    "\n",
    "    def reverse_list(self): \n",
    "        '''\n",
    "            Take a list and reverse it so that end it now the front.\n",
    "            Time Complexity: O(n)\n",
    "        '''  \n",
    "        \n",
    "        # define two nodes, the first node and the node after the first.\n",
    "        p_node = self.head\n",
    "        q_node = p_node.next_node\n",
    "        \n",
    "        # take the start node and have it point to nothing (the end)\n",
    "        p_node.next_node = None\n",
    "        \n",
    "        # then have it's previous node point to the q_node. (the one after the first)\n",
    "        p_node.prev_node = q_node\n",
    "        \n",
    "        # keep going till the end\n",
    "        while q_node is not None:\n",
    "            \n",
    "            # flip the previous with the next\n",
    "            q_node.prev_node = q_node.next_node\n",
    "            \n",
    "            # have the next node point to the p_node\n",
    "            q_node.next_node = p_node\n",
    "            \n",
    "            # now have the p node equal the old q node\n",
    "            p_node = q_node\n",
    "            \n",
    "            # have the q node equal the old q nodes previous node.\n",
    "            q_node = q_node.prev_node\n",
    "        \n",
    "        # redefine the head\n",
    "        self.head = p_node\n",
    "\n",
    "            \n",
    "    \n",
    "    def delete_at_start(self):\n",
    "        '''\n",
    "            Delete the first node.\n",
    "            Time Complexity: O(1)\n",
    "        '''         \n",
    "        \n",
    "        # handle the empty list case\n",
    "        if self.head is None:\n",
    "            print(\"The list has no element to delete\")\n",
    "            return \n",
    "        \n",
    "        # handle the \"only head\" list\n",
    "        if self.head.next_node is None:\n",
    "            self.head = None\n",
    "            return\n",
    "        \n",
    "        # have the head now equal the node after the head\n",
    "        self.head = self.head.next_node\n",
    "        \n",
    "        # make sure that the head's previous node points to none\n",
    "        self.head.prev_node = None\n",
    "\n",
    "        \n",
    "        \n",
    "    def delete_at_end(self):\n",
    "        '''\n",
    "            Delete the last node.\n",
    "            Time Complexity: O(n), I have to find the end first then delete. The delete operation is O(1),\n",
    "                             but the access is O(n). If I knew the end before hand then it could be O(1), for example\n",
    "                             we know the tail.\n",
    "        '''  \n",
    " \n",
    "        # handle the empty list case\n",
    "        if self.head is None:\n",
    "            print(\"The list has no element to delete\")\n",
    "            return\n",
    "        \n",
    "        # handle the \"only head\" list\n",
    "        if self.head.next_node is None:\n",
    "            self.head = None\n",
    "            return\n",
    "        \n",
    "        # grab the first node.\n",
    "        curr = self.head\n",
    "        \n",
    "        # traverse till you get to the end.\n",
    "        while curr.next_node is not None:\n",
    "            curr = curr.next_node\n",
    "        \n",
    "        # grab the previous node of the last node and have it's next node point to nothing.\n",
    "        curr.prev_node.next_node = None\n",
    "        \n",
    "    def remove_duplicates(self):\n",
    "        '''\n",
    "            Remove all the duplicate values from the list.\n",
    "            Time Complexity: O(n)\n",
    "        '''\n",
    "        \n",
    "        # grab the first node and the node after the first\n",
    "        previousNode = self.head\n",
    "        currentNode = previousNode.next_node\n",
    "        \n",
    "        if previousNode == None:\n",
    "            print(\"The list has no elements to delete\")\n",
    "            return            \n",
    "        \n",
    "        # build a set to store non-duplicate values\n",
    "        keys = set([previousNode.data])\n",
    "        \n",
    "        while currentNode:\n",
    "            \n",
    "            data = currentNode.data\n",
    "            \n",
    "            # if it is a duplicate\n",
    "            if data in keys:\n",
    "                \n",
    "                # have the previous node's next pointer by pass the current node and point to the node after it.\n",
    "                previousNode.next_node = currentNode.next_node\n",
    "                \n",
    "                # handle the situation where we aren't at the end.\n",
    "                if previousNode.next_node != None:\n",
    "                    \n",
    "                    # make sure to reassign the previous pointer.\n",
    "                    previousNode.next_node.prev_node = previousNode\n",
    "                    \n",
    "                # set up for th next loop\n",
    "                currentNode = currentNode.next_node\n",
    "                \n",
    "            else:\n",
    "                \n",
    "                # in this case we found a unique value, so add it to the set.\n",
    "                keys.add(data)\n",
    "                \n",
    "                # reassign the nodes\n",
    "                previousNode = currentNode\n",
    "                currentNode = currentNode.next_node\n",
    "                \n",
    "        \n",
    "    def delete_element_by_value(self, x):        \n",
    "        '''\n",
    "            Delete the last node.\n",
    "            Time Complexity: search time + O(1)\n",
    "        ''' \n",
    "        \n",
    "        # handle the empty case list\n",
    "        if self.head is None:\n",
    "            print(\"The list has no element to delete\")\n",
    "            return\n",
    "        \n",
    "        # handle the \"only head\" list\n",
    "        if self.head.next_node is None:\n",
    "            \n",
    "            # check if the value matches, if it does delete node.\n",
    "            if self.head.data == x:\n",
    "                self.head = None\n",
    "            else:\n",
    "                print(\"Item not found\")\n",
    "            return \n",
    "\n",
    "        # handle the \"the first value matches\" case\n",
    "        if self.head.data == x:\n",
    "            self.head = self.head.next_node\n",
    "            self.head.prev_node = None\n",
    "            return\n",
    "\n",
    "        # grab the first node\n",
    "        n = self.head\n",
    "        \n",
    "        # traverse the list\n",
    "        while n.next_node is not None:\n",
    "\n",
    "            # if the value matches\n",
    "            if n.data == x:\n",
    "                break\n",
    "                \n",
    "            # grab the next node\n",
    "            n = n.next_node\n",
    "\n",
    "        # handle the case that we found it in the middle of the list.\n",
    "        if n.next_node is not None:\n",
    "\n",
    "            # grab the previous node's next node and have it point to the node after the one that contains the value\n",
    "            n.prev_node.next_node = n.next_node\n",
    "            # grab the next node's previous node and have it point to the node before the one that contains the value\n",
    "            n.next_node.prev_node = n.prev_node\n",
    "\n",
    "        else:\n",
    "\n",
    "            # otherwise the value is at the end.\n",
    "            if n.data == x:\n",
    "                # so just take the node's previous node, grab it's next node and have it point to nothing.\n",
    "                n.prev_node.next_node = None\n",
    "            else:\n",
    "                print(\"Element not found\")\n",
    "                \n",
    "    def rotate_list(self, k):\n",
    "        '''\n",
    "            Rotate a list so that the first K elements are now at the end of the list.\n",
    "            Time Complexity: O(n)\n",
    "        ''' \n",
    "        \n",
    "        # handle the case where k is less than or equal to 0\n",
    "        if (k <= 0) or (k > self.get_list_size()):\n",
    "            print('The K you chosen is not correct, please choose a postive k that is less than size of the list.')\n",
    "            return\n",
    "        \n",
    "        # grab the head\n",
    "        curr = self.head\n",
    "        \n",
    "        # traverse the list till either you reach the end or the kth element.\n",
    "        count = 1\n",
    "        while (count < k and curr != None):\n",
    "            curr = curr.next_node\n",
    "            count = count + 1\n",
    "            \n",
    "        # if kth element is none, exit.\n",
    "        if curr is None:\n",
    "            return\n",
    "        \n",
    "        # assign the kth element to a new variable\n",
    "        kthNode = curr\n",
    "        \n",
    "        # traverse to the end of the list\n",
    "        while curr.next_node is not None:\n",
    "            curr = curr.next_node\n",
    "            \n",
    "        # assign the node after the last node to the original head.\n",
    "        curr.next_node = self.head\n",
    "        \n",
    "        # have the original head's previous node now point to the last node.\n",
    "        self.head.prev_node = curr\n",
    "        \n",
    "        # have the head now point to the node after the kth element.\n",
    "        self.head = kthNode.next_node\n",
    "        \n",
    "        # have the head's previous node equal none.\n",
    "        self.head.prev_node = None\n",
    "        \n",
    "        # have the node after the end of the list equal none.\n",
    "        kthNode.next_node = None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "----------------------------------------------------------------------------------------------------\n",
      "After Insertion\n",
      "----------------------------------------------------------------------------------------------------\n",
      "70\n",
      "80\n",
      "90\n",
      "90\n",
      "90\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After Insertion Before\n",
      "----------------------------------------------------------------------------------------------------\n",
      "70\n",
      "50\n",
      "80\n",
      "90\n",
      "90\n",
      "90\n",
      "----------------------------------------------------------------------------------------------------\n",
      "Before Reversal\n",
      "----------------------------------------------------------------------------------------------------\n",
      "70\n",
      "50\n",
      "70\n",
      "70\n",
      "80\n",
      "90\n",
      "90\n",
      "90\n",
      "100\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After Reversal\n",
      "----------------------------------------------------------------------------------------------------\n",
      "100\n",
      "90\n",
      "90\n",
      "90\n",
      "80\n",
      "70\n",
      "70\n",
      "50\n",
      "70\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After Head Deletion\n",
      "----------------------------------------------------------------------------------------------------\n",
      "90\n",
      "90\n",
      "90\n",
      "80\n",
      "70\n",
      "70\n",
      "50\n",
      "70\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After Tail Deletion\n",
      "----------------------------------------------------------------------------------------------------\n",
      "90\n",
      "90\n",
      "90\n",
      "80\n",
      "70\n",
      "70\n",
      "50\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After Specific Deletion\n",
      "----------------------------------------------------------------------------------------------------\n",
      "90\n",
      "90\n",
      "80\n",
      "70\n",
      "70\n",
      "50\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After Duplicate Deletion\n",
      "----------------------------------------------------------------------------------------------------\n",
      "90\n",
      "80\n",
      "70\n",
      "50\n",
      "100\n",
      "----------------------------------------------------------------------------------------------------\n",
      "After List Rotation\n",
      "----------------------------------------------------------------------------------------------------\n",
      "70\n",
      "50\n",
      "100\n",
      "90\n",
      "80\n"
     ]
    }
   ],
   "source": [
    "# define a new list\n",
    "double_list = DoubleLinkedList()\n",
    "\n",
    "# insert a value at the beginning\n",
    "double_list.insert_beg(90)\n",
    "double_list.insert_beg(90)\n",
    "double_list.insert_beg(90)\n",
    "double_list.insert_beg(80)\n",
    "double_list.insert_beg(70)\n",
    "\n",
    "print('-'*100)\n",
    "print('After Insertion')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# define a node\n",
    "first_node = double_list.head.next_node\n",
    "\n",
    "# insert before that node\n",
    "double_list.insert_before(first_node, 50)\n",
    "\n",
    "print('-'*100)\n",
    "print('After Insertion Before')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# insert a value at the end\n",
    "double_list.insert_end(100)\n",
    "\n",
    "# define another node\n",
    "my_node = double_list.head.next_node\n",
    "\n",
    "# insert a value after that node\n",
    "double_list.insert_after(my_node, 70)\n",
    "double_list.insert_after(my_node, 70)\n",
    "\n",
    "# print the list\n",
    "print('-'*100)\n",
    "print('Before Reversal')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# reverse the list\n",
    "double_list.reverse_list()\n",
    "print('-'*100)\n",
    "print('After Reversal')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# delete the first value\n",
    "double_list.delete_at_start()\n",
    "\n",
    "print('-'*100)\n",
    "print('After Head Deletion')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# delete the last value\n",
    "double_list.delete_at_end()\n",
    "\n",
    "print('-'*100)\n",
    "print('After Tail Deletion')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# delete specific value\n",
    "double_list.delete_element_by_value(90)\n",
    "\n",
    "print('-'*100)\n",
    "print('After Specific Deletion')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "double_list.insert_end(100)\n",
    "double_list.insert_end(100)\n",
    "\n",
    "# delete duplictes\n",
    "double_list.remove_duplicates()\n",
    "\n",
    "print('-'*100)\n",
    "print('After Duplicate Deletion')\n",
    "print('-'*100)\n",
    "double_list.traverse()\n",
    "\n",
    "# rotate list\n",
    "double_list.rotate_list(2)\n",
    "\n",
    "print('-'*100)\n",
    "print('After List Rotation')\n",
    "print('-'*100)\n",
    "double_list.traverse()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
